package q547_findCircleNum;

import java.util.LinkedList;
import java.util.Queue;

public class Solution_2 {
    /*
    此题的BFS相较于其他的有所不同
    一般来说广度优先搜索是先确定首次压入队列的所有元素 然后开始搜索
    但是此题需要在循环中进行判断 再进行搜索
     */
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visited = new boolean[cities];
        int provinces = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < cities; i++) {
            // 首先判断当前城市是否已经被记录过了
            if (!visited[i]) {
                // 如果没有 再开始搜索
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;

                    // 广度搜索的逻辑 如果发现有相连的城市 并且没有被记录过
                    // 就将其加入到队列中 随着队列反复进出 就可以识别每一个省份包含的所有城市
                    for (int k = 0; k < cities; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }

                // 最后加入ans
                provinces++;
            }
        }
        return provinces;
    }

}
